from typing import List


'''
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
'''

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if len(nums) == 1: return nums[0]
        r = [0] * (max(nums) + 1)
        re = []
        for i in range(len(nums)):
            r[nums[i]] += nums[i]
            if nums[i] not in re:
                re.append(nums[i])
        re.sort()

        dp = [0] * len(r)
        dp[0] = r[0]
        dp[1] = max(r[0], r[1])
        for i in range(2, len(r)):
            dp[i] = max(dp[i-2] + r[i], dp[i-1])
        
        return dp[-1]

    def rob(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
        
        return dp[-1]

    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[1] * n for _ in range(m)]

        print(dp)
        for i in range(0, m):
            for j in range(0, n):
                if i == 0 and j == 0: continue
                if obstacleGrid[i][j] == 1: dp[i][j] = 0
                else:
                    up, left = 0, 0
                    if i >= 1: 
                        print(dp[i-1][j])
                        up = dp[i-1][j]
                    if j >= 1: 
                        print(dp[i][j-1])
                        left = dp[i][j-1]
                    dp[i][j] = up + left

        print(dp)
        return dp[m - 1][n - 1]
    
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        m = len(triangle)
        dp = []
        dp.append(triangle[0])
        for i in range(1, m):
            dp.append([0 for _ in range(len(triangle[i]))])

        for i in range(1, m):
            n = len(triangle[i])
            for j in range(0, n):
                left = 2<<1024
                right = 2<<1024
                if j >= 1:
                    left = dp[i - 1][j - 1] + triangle[i][j]
                if j < n - 1: 
                    right = dp[i - 1][j] + triangle[i][j]
 
                dp[i][j] = min(left, right)

        print(dp)
        return min(dp[m - 1])
    
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        for i in range(1, m):
            for j in range(0, m):
                left = 2<<12
                mid = 2<<12
                right = 2<<12
                if j >= 1:
                    left = matrix[i - 1][j - 1] + matrix[i][j]
                mid = matrix[i - 1][j] + matrix[i][j]
                if j < m - 1: 
                    right = matrix[i - 1][j + 1] + matrix[i][j]
 
                matrix[i][j] = min(left, mid, right)

        return min(matrix[m - 1])

    
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        
        
        return dp[0][n - 1]

    def largestTriangleArea(self, points: List[List[int]]) -> float:
        n = len(points)
        res = 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    x1, y1 = points[i]
                    x2, y2 = points[j]
                    x3, y3 = points[k]
                    area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
                    res = max(res, area)

        return res

    
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1


if __name__ == '__main__':
    solution = Solution()
    points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
    print(solution.largestTriangleArea(points))